1. Field of the Invention
The invention relates generally to compressing computer graphics information. More particularly, the invention relates to a system and method for compressing computer graphics and textures for three dimensional computer graphics.
2. Background Information
In order to provide realistic computer graphics with smooth continuous rendering rates, it is desirable to have fast access to a large number of high-quality detailed textures. This goal is somewhat constrained by system memory and memory access bandwidth limitations. Texture compression can be used to significantly reduce the memory required to store textures and the bandwidth required to access textures from memory. Thus, four qualities are typically important for texture compression methods: (1) high compression ratio, (2) sufficient quality of decompressed images, (3) fast decoding, and (4) fast access to any texel in any order. Methods having these qualities allow more and higher-resolution textures to be incorporated into graphics, and provide a more realistic, immersing experience.
Block decomposition is one approach to texture compression. This approach is based on dividing an image into equally sized blocks (typically, 4xc3x974 texels) and storing each of them in a uniform manner, so that after compression each block takes the same amount of memory. Thus, all blocks may be stored row by row, and an offset of a block containing any individual texel may be easily calculated. Three prior art block-decomposition methods will be discussed below: (1) Microsoft""s Texture and Rendering Engine Compression (TREC), (2) S3 Texture Compression (S3TC), and (3) 3dfx""s Texture Compression (FXT1).
Texture and Rendering Engine Compression (TREC) was developed by Microsoft Corporation. This technique is very similar to the JPEG standard since it is based on the two-dimensional discrete cosine transform (DCT) of 8xc3x978 pixel blocks and quantization of coefficients. This approach provides variable compression ratios with satisfactory visual quality. However, implementing a hardware DCT decoder on a graphics accelerator board only for texture decompression is relatively expensive.
FIG. 1 shows a representative indexed texture block 110 for compression of a 4xc3x974 texel texture block according to the S3TC approach. This approach stores two color values 115 for the texture block. A reconstructed color palette 120, corresponding to indexed texture block 110, contains the two stored color values 115 and two interpolated colors 140. The interpolated color values 140 are determined by equations 160. A two-bit index 170 (e.g., 00, 01, 10, 11) is assigned to each of the texels in block 110, wherein each of the indices represents a color value in one of the four color palette entries 130 in the reconstructed color palette 120.
Because colors are stored in RGB565 format, palette information requires 32 bits per each texture block (two colors times 16 bits per color). Indices take another 32 bits per block (16 texels times 2 bits per texel). Thus, the compressed texture block requires 8 bytes, while the original takes 48 considering RGB888. Consequently, S3TC scheme provides 6:1 compression ratio.
FXT1 may be considered an extension of the S3TC approach, since it separately encodes equally sized blocks of 4xc3x978 texels by small local palettes (look-up tables). FXT1 has four modifications, however all the modifications have a common approach: (1) some basic colors (RGB555) are stored in a block, (2) a local palette (or palettes) is generated by interpolation of basic colors, and (3) each texel is represented by index of the most appropriate color from the corresponding look-up table.
FIG. 2 briefly presents the FXT1 encoding parameters for different modifications. For CC_HI scheme, two basic RGB555 colors, which are stored in a block, are used for interpolating seven RGB888 look-up table entries, while the eighth entry is defined transparent. Thus, three bits are required for each texel. CC_CHROMA refers to storing four colors, which are used with no change as the four-entry palette. CC_MIXED is very similar to the S3TC approach, since two four-entry palettes are generated, each by interpolating between two colors (therefore, four colors are stored for a 4xc3x978 texel block). Then, two sub-blocks of 4xc3x974 texels are encoded separately by their own palettes. CC_ALPHA creates an aggregate of two 4xc3x974 texel texture blocks and stores three colors for that aggregate. The first and second colors are used as the primary colors of the left 4xc3x974 texel texture block and the second and third colors are used as the primary colors of the right 4xc3x974 texel texture block. Two additional colors are created for each texture block by interpolating between the two primary colors for that block. During compression, FXT1 encoder produces all representations of each 4xc3x978 block of texels, chooses the one that introduces the least error, and stores the corresponding data in the resulting data stream.
Thus, S3TC represents each block of 4xc3x974 texels by 8 bytes (4 for colors +4 for indices), while FXT1 uses a 16-byte data chunk for each 4xc3x978 texel block. The compression ratio, provided by these techniques, is 6:1 for TrueColor 24 bpp images, and 8:1 for 32 bpp images.
One major problem with current texture compression methods including S3TC and FXT1 is an inadequate balance between visual quality and compression ratio. In the prior art, high compression ratio is achieved by serious reduction of color data available for texel representation. In general, the methods described above use interpolation to determine some colors, and the interpolated colors lack diversity. As a result, less independent colors are available to represent the image, and this may introduce perceptible quality degradation in some cases.
As an example, consider an image having three colors that do not belong to one line in an RGB cube. For instance, it may be red, green and blue. If pixels of these colors appear in one block simultaneously, many prior art methods will not be able to reproduce them without visual degradation by interpolation of any two. It will either discard less frequent color or construct a line (in an RGB cube) being less distant from all existing points. This will often introduce perceptible quality degradation effects as shown in FIG. 3. FIG. 3 shows an original image 310 where shades of gray are used for representing a red flower 320 with a blue core 330. As shown for the S3TC method of compression 340, compression and reconstruction using S3TC resulted in regions with quality degradation 360 because only two basic independent colors were available.